package leetcode.top100;

import org.checkerframework.checker.units.qual.A;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2022/10/20 1:11 PM
 * @description：
 */
public class _101_最长公共子串 {
    @Test
    public void test() {
        System.out.println(new Solution().maxSubString("abcdefgad", "adefgwgewegad"));
    }

    class Solution {
        public String maxSubString(String str1, String str2) {
            int len1 = str1.length();
            int len2 = str2.length();
            int[] dp = new int[len1];
            int[] preRow = new int[len1];
            int maxLen = 0;
            int endIdx = 0;
            for (int i = 0; i < len2; i++) {
                char ch = str2.charAt(i);
                for (int j = 0; j < len1; j++) {
                    if (ch == str1.charAt(j)) {
                        if (j == 0) {
                            dp[j] = 1;
                        } else {
                            dp[j] = preRow[j - 1] + 1;
                        }
                        if (dp[j] > maxLen) {
                            maxLen = dp[j];
                            endIdx = j;
                        }
                    }
                }
                preRow = Arrays.copyOf(dp, len1);
                Arrays.fill(dp, 0);
            }
            System.out.println(maxLen);
            return str1.substring(endIdx - maxLen + 1, endIdx + 1);
        }
    }
}
